// 旋转数组
// Created by madison on 2022/8/28.
//
#include "vector"

using namespace std;

class Solution {
public:
    // 方法一：使用额外的数组
    void rotate(vector<int> &nums, int k) {
        int n = nums.size();
        vector<int> newArr(n);
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        nums.assign(newArr.begin(), newArr.end());
    }

    inline int gcd(int a, int b) {
        return b > 0 ? gcd(b, a % b) : a;
    }

    // 方法二：环状替换
    void rotate1(vector<int> &nums, int k) {
        int n = nums.size();
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                swap(nums[next], prev);
                current = next;
            } while (start != current);
        }
    }

    void reverse(vector<int> &nums, int starat, int end) {
        while (starat < end) {
            swap(nums[starat], nums[end]);
            starat += 1;
            end -= 1;
        }
    }

    // 方法三：数组翻转
    void rotate2(vector<int> &nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
};

int main() {
    Solution solution;
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
    solution.rotate1(nums, 3);
    for (auto &num: nums) {
        printf("%d\t", num);
    }
    return 0;
}
